\newpage
\part{Der RSA-Algorithmus}
%
\input{./mathematische_verfahren.tex}
%
\input{./schluessel.tex}
%
%***************************************
% Verschlüsselung und Entschlüsselung
%***************************************
\subsection{Formel Verschlüsselung}
Sind die Schlüssel erstellt, kann ein Text m einfach verschlüsselt werden.\\
Dazu dient folgende Formel:
%
\begin{equation}
  c \equiv m^e  \bmod(N)
  \label{eqn:rsa_encription}
\end{equation}
%
%\subsection{RSA Entschlüsselung}
%Die RSA Entschlüsselung ist ohne den Geheimschlüssel zu wissen nicht möglich. Da die Sicherheit von diesem Geheimschlüssel abhängt, gilt es diesen möglichst lang zu wählen und geheim zu halten. Aktuell gilt eine Schlüssellänge von 2048 Bit als sicher. Als Dezimalzahl ausgedrückt, ist dies eine Zahl von $ 3,2 \cdot 10^{616} $
%Die Angriffe auf die RSA Verschlüsselung zielen darauf ab, den Geheimschlüssel zu ermitteln. Das Problem dabei ist die Primfaktoren Zerlegung von grossen Zahlen. Mehr dazu im Kapitel Angriffe %Verweis%

\subsection{Formel Entschlüsselung}
Die Entschlüsselung der Nachricht wird mit folgender Formel realisiert:
%
\begin{equation}
  m \equiv c^d \bmod(N)
  \label{eqn:rsa_decription}
\end{equation}
%
%
%***************************************
% BEISPIEL
%***************************************
\section{Beispiel}
Nachdem wir nun die Grundlagen für die Anwendung des RSA-Algorithmus erarbeitet haben, ist es an der Zeit ein kleines Beispiel durchzuführen.
\subsection{Einfaches Zahlenbeispiel}
Wir starten mit einem einfachen Zahlenbeispiel. Auf die mathematischen Methoden wird nur noch verwiesen. Wir erklären sie hier nicht mehr.\\
Für dieses Beispiel nehmen wir die Zahlen
%
\begin{flalign*}
  p = 13 \\
  q = 19
\end{flalign*}
%
\paragraph{Schlüssel-Paar erstellen}
Wir berechnen nun das RSA-Modul N (siehe Formel \ref{eqn:rsa_modul}) und $\varphi(N) $ (siehe Formel \ref{eqn:eulersche_func}) aus p und q.
\begin{equation*}
  \tag{RSA-Modul}
  247 = 13 \cdot 19
\end{equation*}
%
\begin{equation*}
  \tag{$\varphi(N)$}
  216 = (13 - 1) \cdot (19 - 1)
\end{equation*}
%
Zu $ \varphi(N) $ suchen wir uns eine zweite Zahl e, die teilerfremd zu $ \varphi(N) $ ist, sprich den $ggT(\varphi(N),e) = 1$ hat. Am Besten man verwendet für e eine weitere Primzahl.
%
\begin{equation*}
    e = 23
\end{equation*}
%
Der öffentliche Schlüssel $N = 247$ und $e = 23$ ist nun berechnet [siehe Section \ref{sec:public_key}]\\
Um den Entschlüsselungs-Exponenten zu berechnen, müssen wir zuerst den ggT(216,23) (siehe Formel \ref{eqn:euklidischer_algo}) ausrechnen.
\begin{flalign*}
  216 & = 9 \cdot 23 + 9 \\
  23 & = 2 \cdot  9 + 5 \\
  9 & = 1 \cdot  5 + 4 \\
  5 & = 1 \cdot  4 + 1
\end{flalign*}
%
Jetzt wenden wir den Erweiterten Euklidischen Algorithmus (siehe Formel \ref{eqn:erw_euklid_algo}) an.
\begin{flalign*}
  1 &= 5 - 1 \cdot 4 = 5 - 1 \cdot(9 - 1 \cdot 5) = 5 - 1 \cdot 9 + 1 \cdot 5 = 2 \cdot 5 - 1 \cdot 9\\
  &= 2 \cdot 5 - 1 \cdot 9 = 2 \cdot (23 - 2 \cdot 9) - 1 \cdot 9 = 2 \cdot 23 - 4 \cdot 9 - 1 \cdot 9 = 2 \cdot 23 - 5 \cdot 9\\
  &= 2 \cdot 23 - 5 \cdot 9 = 2 \cdot 23 - 5 \cdot (216 - 9 \cdot 23) = 2 \cdot 23 - 5 \cdot 216 + 45 \cdot 23 = \textbf{47} \cdot 23 \textbf{- 5} \cdot 216
\end{flalign*}
Indem wir die Modulare Inverse auf letzte Gleichung anwenden erhalten wir:
\begin{equation*}
  1 \equiv 47 \cdot 23 \bmod(216)
\end{equation*}
Und dadurch unseren privaten Schlüssel $d = 47$ und $N = 216$.\\
%
Jetzt haben wir unseren privaten als auch öffentlichen Schlüssel die wir für eine Ver- Entschlüsselung benötigen.
\paragraph{Verschlüsseln}
Wir verschlüsseln die Zahl 15\\
Verschlüsselungsfunktion anwenden siehe Formel \ref{eqn:rsa_decription}
\begin{equation*}
  15^{23} \bmod (247) = 59
\end{equation*}
Die Zahl 15 verschlüsselt mit unserem öffentlichen Schlüssel (23, 247) ergibt die Zahl 59.
%
\paragraph{Entschlüsseln}
Um zu überprüfen ob unserer privater Schlüssel auch wirklich funktioniert, entschlüsseln wir die Zahl 59 mit unserem privaten Schlüssel. Siehe Formel \ref{eqn:rsa_decription}\\
\begin{equation*}
  59^{47} \bmod (247) = 15
\end{equation*}
Als Resultat erhalten wir 15 und stellen fest, dass unser kleines Beispiel funktioniert hat.
%
% Beispiel TEXT
%
\subsection{Beispiel an einem Text}
Wir wenden ein Beispiel an einem Text an. Da Buchstaben nicht verschlüsselt werden können, denn mit ihnen lässt sich nicht rechnen, müssen wir den Text in Zahlen umwandeln. Dafür gibt es einige Möglichkeiten. Wir verwenden in diesem Beispiel die \textit{ASCII-Tabelle}\footnote{Die ASCII-Tabelle ordnet jedem Buchstaben eine eindeutige Zahl zu.}.\\
Weiter gilt zu beachten, dass man bei Text-Verschlüsselungen grössere Schlüssel braucht. Deshalb nehmen wir für das nächste Beispiel neue Zahlen:
\begin{flalign*}
  p &= 101\\
  q &= 349\\
  N &= 35'249\\
  \varphi(N) &= 34'800\\
  e &= 509\\
  d &= 7'589
\end{flalign*}
Wir verschlüsseln das Wort \textit{GIBM MUTTENZ}. Als erstes müssen wir unseren Text in Zahlen umwandeln.\\
\textit{GIBM MUTTENZ} würde in der ASCII-Schreibweise \textit{717366773277858484697890} heissen.\\
Da $m < N$ sein muss, müssen wir unsere grosse Zahl in Blöcke aufteilen. Wir machen uns immer vierer Blöcke und verschlüsseln sie einzeln mit unserem öffentlichen Schlüssel (35'249, 509).
\begin{flalign*}
  7173^{509} \bmod(35'249) &= 2330\\
  6677^{509} \bmod(35'249) &= 21891\\
  3277^{509} \bmod(35'249) &= 10955\\
  8584^{509} \bmod(35'249) &= 403\\
  8469^{509} \bmod(35'249) &= 32164\\
  7890^{509} \bmod(35'249) &= 34762
\end{flalign*}
Der verschlüsselte Text \textit{233021891109554033216434762} kann somit zum Empfänger gesendet werden.\\
Leider gibt es nicht immer gleich lange Zahlen. Das wird dann zum Problem, wenn wir den verschlüsselten Text entschlüsseln. Dieses Problem wird bei der Implementierung der Verschlüsselung gelöst. Entweder werden die Zahlen aufgefüllt, oder man verwendet ein eindeutiges Trennzeichen.\\
Der Empfänger entschlüsselt jetzt mit seinem private Key (35'240, 7589) die Nachricht. Damit er die Originalnachricht erhaltet, müssen die gleichen Blöcke genommen werden, wie bei der Verschlüsselung.
%
\begin{flalign*}
  2330^{7589} \bmod(35'249) &= 7173\\
  21891^{7589} \bmod(35'249) &= 6677\\
  10955^{7589} \bmod(35'249) &= 3277\\
  403^{7589} \bmod(35'249) &= 8584\\
  32164^{7589} \bmod(35'249) &= 8469\\
  34762^{7589} \bmod(35'249) &= 7890
\end{flalign*}
%
Der Empfänger hat seine geheime Nachricht erfolgreich entschlüsseln können. 
%
%
\newpage
%******************************************************************************
% Mathematischer Nachweis (Beweis war zu hoch gegriffen)
%******************************************************************************
\section{Mathematischer Nachweis der Funktionsweise}
Dieses Kapitel wurde mit Hilfe des Buches \textit{Kryptologie} \cite{kryptologie} erstellt.\\[2ex]
%
Nachdem wir die Webseite überprüft haben und auch ein Buch gefunden haben, welches im Quellenverzeichnis auf diese Webseite verweist, können wir davon ausgehen, dass diese Informationen gut recherchiert sind. \\
%TODO: Zusätzliches Buche angeben mit Beweis\\
Bisher nahmen wir an, dass der RSA-Algorithmus korrekt arbeitet. Auf diese Annahme möchten wir nun eingehen und aufzeigen, warum der Algorithmus funktioniert. Der Algorithmus arbeitet korrekt, wenn die Verschlüsselung und nachherige Entschlüsselung wieder das gleiche ergibt. Dies darf nur mit dem passenden privaten und öffentlichen Schlüssel möglich sein.\\
Auf das vorherige, erarbeitete Wissen wird nicht mehr im Detail eingegangen. \\
Folgende Zusatzbedingungen müssen beim RSA-Algorithmus zwingend eingehalten werden:
\begin{enumerate}
  \item Die Nachricht muss immer kleiner als das RSA-Modul N gewählt werden.
  \item Die Nachricht muss grösser als 1 sein.
\end{enumerate}
%
%
\subsection{Verschlüsselung und Entschlüsselung gleichsetzen}
Für den Nachweis benötigen wir die ursprünglichen Formeln zur Verschlüsselung (siehe Formel \ref{eqn:rsa_encription}) und Entschlüsselung (siehe Formel \ref{eqn:rsa_decription}). Diese lauten:
\begin{flalign*}
  c & \equiv m^e \bmod(N) \\
  m & \equiv c^d \bmod(N)
\end{flalign*}
Da in beiden Formeln die Ursprungsnachricht m und die verschlüsselte Nachricht c vorkommen, können wir diese Formeln gleichsetzen. Dazu lösen wir die Entschlüsselungsformel nach c auf:
\begin{flalign*}
  m &\equiv c^d \bmod(N) \\
  m &= c^d - k \cdot N \\
  m + k \cdot N &= c^d \\
  \sqrt[d]{m' + k \cdot N} &= c = m^e \bmod(N)
\end{flalign*}
Modulo ergibt jeweils den Rest einer ganzzahligen Division. Durch Umformung kann diese jeweils als $ k \cdot N $ dargestellt werden, wobei k eine ganze Zahl sein muss.
%
\newpage
%
Nun können wir c durch $ \sqrt[d]{m + k \cdot N} $ in der Verschlüsselungsformel \ref{eqn:rsa_encription} einsetzen.
%Wir setzen nun die beiden Formeln gleich, so das nur noch die Ursprungsnachricht m in der Gleichung vorhanden ist:
\begin{flalign*}
  m^e \bmod(N) &\equiv \sqrt[d]{m' + k \cdot N} \\
  {m^{e} \bmod(N)}^d &\equiv m' + k \cdot N \\
  m^{e \cdot d} \bmod(N) &\equiv m' + k \cdot N \\
  m^{e \cdot d} \bmod(N) &\equiv m' 
  %{m^e}^d mod N & = m \\
  %{m^d}^e mod N & = m
\end{flalign*}
Wir möchten aufzeigen warum $ {m^{e} \bmod(N)}^d $ auch als $ {m^{e \cdot d} \bmod(N)} $ dargestellt werden kann:\\
Falls $m^e$ kleiner oder gleich $N$ ist, kann die Formel auch so dargestellt werden $ {m^e + 0 \cdot N}^d $. Nun kann $ 0 \cdot N  $ gestrichen werden.
Falls $m^e$ grösser als $N$ ist, müssen wir die Erklärung über die identische Restklasse geben. Dazu überlegen wir uns falls $m^e$ durch $N$ teilbar ist, wäre der Rest immer 0. Hier ein kleines Zahlenbeispiel:
%
\begin{equation*}
5^6 \bmod(5) \equiv 0
\end{equation*}
%
und
%
\begin{equation*}
 5^3 \bmod(5) \equiv 0
\end{equation*}
%
Beim RSA-Algorithmus ist $m^e$ meistens nicht durch N teilbar, aus vorheriger Überlegung resultiert daraus, dass immer der selbe Rest übrig bleibt. Als Beispiel:
%
\begin{equation*}
 5^6 \bmod(4) \equiv 1
\end{equation*}
%
und 
%
\begin{equation*}
5^3 \bmod(4) \equiv 1
\end{equation*}
%
%und $m^{e \cdot d}$ können beide mit dem gleichen Rest durch N geteilt werden. Dies liegt daran, dass beide in der gleichen Restklasse sind. Dies können wir durch folgende Überlegung nachweisen:\\
%Falls ein vielfaches von a durch a geteilt wird, gibt dies immer Rest 0. In einer Formel ausgedrückt: $ a^b mod a = 0 $. Dies ist logisch, da das vielfache von a immer ebenfalls Rest 0 geteilt werden kann. In unserem Fall geben wir den Rest von $m^e$ und $m^{e \cdot d}$ aus, welches nicht durch N teilbar ist. 
Die Formel $ m^{e \cdot d} \bmod(N) \equiv m + k \cdot N $ kann gekürzt werden, da $ k = 0 $ sein muss. Dies liegt daran, dass wir auf der rechten Seite mit Modulo N den Rest ausgeben. Der Rest kann 0 bis N-1 gross sein. Da m einen Wert hat, muss k in diesem Fall 0 sein. \\
Wir möchten aufzeigen, dass die Verschlüsselung (hoch e) und nachherige Entschlüsselung (hoch d) wieder die ursprüngliche Nachricht ergibt:
\begin{equation*}
 m^{e \cdot d} \bmod(N) \equiv m' 
\end{equation*}
%
\newpage
%
%\subsection{Grundlagen zur Erklärung}
%Für den Beweis benötigen wir vorherige Kenntnisse und bestimmte Sätze. Diese möchten wir hier nochmals kurz in Erinnerung rufen.\\ 
%Das RSA-Modul N wird aus den ausgewählten Primzahlen p und q erstellt.
%\begin{equation*}
%  N = p \cdot q
%\end{equation*}
%
%e wurde teilerfremd zu $ \varphi(n) $ gewählt. 
%$ \varphi(n) = (p-1) \cdot (q-1) $
%
%Zusätzlich wurde d so gewählt, dass folgendes zählt:
%\begin{equation*}
% e \cdot d + k \cdot \varphi(N) = 1 = ggT(e,\varphi(N))
%\end{equation*}
%
%Für den Beweis müssen wir ausschweifen auf den Satz von Euler Fermat. Dieser bildet die Grundlage zur RSA-Verschlüsselung. Er lautet wie folgt:
%\begin{equation*}
%	a^{\varphi(n)} \equiv 1\,(\mathrm{mod}\,n)
%\end{equation*}
%Da wir mit Primzahlen arbeiten, kann dieser Satz auch anders ausgedrückt werden. $ \varphi(n) $ gibt alle teilerfremden Zahlen zu n an. Da n durch zwei Primzahlen gebildet wurde, gibt es $ (p-1) \cdot (q-1) $ teilerfremde Zahlen. 
%
\subsection{Nachweis der Funktionsweise}
Die Gleichsetzung der Entschlüsselung und Verschlüsselung dient uns als Grundlage des Nachweises:
\begin{equation*}   
 m^{e \cdot d} \bmod(N) \equiv m'
\end{equation*}
%
Durch die Anwendung des erweiterten Euklidischen Algorithmus (siehe Kapitel \ref{eqn:erw_eukl_fertig}) bei der Erstellung des Schlüssels (siehe Kapitel \ref{eqn:rsa_private_key_erstellen}) wurde folgendes bestimmt:
%Wir könnnen durch die modulare Inverse $ e \cdot d $ anders ausdrücken, siehe [\ref{eqn:mod_inverse}]. Diese lösen wir nach $ e \cdot d $ auf:\\
\begin{flalign*}
 e \cdot d &\equiv 1 \bmod(\varphi(N))  \\
 % e \cdot d + k \cdot \varphi(N) &= 1  \\
 e \cdot d &= 1 + k \cdot \varphi(N) \\
 e \cdot d &= k \cdot \varphi(N) + 1
\end{flalign*}
Wenn die Formel Modulo beinhaltet, kann diese jeweils auch mit k Mal den Rest ausgedrückt werden. \\
%
Nun ersetzen wir in unserer Ausgangslage $ e \cdot d $ durch $ k \cdot \varphi(N)+1 $ und lösen die Gleichung auf:
\begin{flalign*}
 m^{e \cdot d} \bmod(N) &\equiv m' \\
 m^{ k \cdot \varphi(N) + 1} \bmod(N) &\equiv m'  \\
 m^{k \cdot \varphi(N)} \cdot m \bmod(N) &\equiv m'  \\
 { m^{ \varphi(N) }} ^k \cdot m \bmod(N) &\equiv m' \\
 %{ m^{ \varphi((p-1)\cdot(q-1)) }} ^k \cdot m \bmod((p-1)\cdot(q-1)) &\equiv m'
\end{flalign*}
%
%Durch den kleinen Satz von Fermat wissen wir dass $ \varphi(N) $ 1 sein muss. 
Mit dem Satz von Euler können wir nun nach $ m^{\varphi(N)} $ auflösen. (siehe Satz von Euler Formel \ref{eqn:satz_von_euler} und Formel \ref{eqn:eulersche_func}).
%TODO: Kleiner Satz von Fermat erklären
\begin{flalign*}
%  m^{(p-1)} &= 1 \bmod p \\
  m^{(p-1) \cdot (q-1)} &= 1 \bmod(p \cdot q) \\
  m^{\varphi(N)} &= 1 \bmod(N)
\end{flalign*}
%
%\begin{enumerate}
%1. Die Nachricht hoch die Anzahl der Teilerfremden Zahlen bei einer Primzahl ergibt 1 Modulo die Zahl \\
%\item Der Satz von Euler in Anwendung auf den RSA-Algorithmus kann Bei der RSA-Verschlüsselung haben wir die Kombination aus zwei Primzahlen.
%nicht hoch eine Primzahl gerechnet, sondern hoch $ (p-1) \cdot (q-1) $. 
%Daher können wir laut dem Satz von Euler die Gleichung so darstellen wie oben dargestellt.
%\item $ p \cdot q $ ist das RSA-Modul N, siehe \ref{eqn:rsa_modul}. $ (p-1) \cdot (q-1) $ sind die Teilerfremden Zahlen von N, da es sich bei p und q um Primzahlen handelt, siehe Eulersche Funktion \ref{eqn:eulersche_func}.
%\end{enumerate}
%
Daraus resultiert das $ 1 \bmod(N) $ das gleiche ist wie $ m^{\varphi(N)} $ und entsprechend eingesetzt werden kann. Danach lösen wir die Formel auf. 
\begin{flalign*}
 { m^{ \varphi(N) }} ^k \cdot m \bmod(N) &\equiv m'  \\
 {1 \bmod(N) }^k \cdot m \bmod(N) &\equiv m'  \\
 1^k \cdot m \bmod(N) &\equiv m' \\
 1 \cdot m \bmod(N) &\equiv m' \\
 m + x \cdot N &= m' \\
 m + 0 \cdot N &= m' \\
 m &= m' 
\end{flalign*}
$ 1 \bmod(N) $ muss 1 ergeben, da der Rest höchstens 1 sein kann und das RSA-Modul N grösser als 1 ist. (siehe Formel \ref{eqn:rsa_modul}) \\
$ 1^k $ ergibt immer 1, da die Basis 1 hoch ein beliebiger Exponent 1 ergibt. \\
Wir wissen das $ x = 0 $ sein muss, da m immer kleiner als N gewählt wird (Siehe Zusatzbedingung 1). 
Falls m gleich N ist, würde nach der Verschlüsselung 0 herauskommen und die Entschlüsselung somit nicht mehr funktionieren. Falls m grösser als N ist wäre die Nachricht nach der Verschlüsselung nicht wieder korrekt zu entschlüsseln. In diesem Fall wird die Nachricht aufgeteilt und später wieder zusammengesetzt. \\
Schlussendlich stellen wir fest, dass $m = m'$ ist und weisen somit die korrekte Funktionsweise des RSA-Algorithmus nach. Die Verschlüsselung und darauffolgende Entschlüsselung ergibt wieder die Ursprungsnachricht.\\
Die Entschlüsselung der Nachricht funktioniert nur mit dem zugehörigen privaten Schlüssel, da mit dem euklidischen Algorithmus, d so bestimmt wurde, das folgendes zählt:
\begin{flalign*}
 e \cdot d + k \cdot \varphi(N) &= 1	
\end{flalign*}
Mit der Modularen Inverse wurde d als positive Zahl bestimmt. Aus dieser Formel ist ersichtlich, dass nur ein ganz bestimmtes d zu einem e und N gehört. Jeder andere Entschlüsselungs-Exponent d würde die Formel nicht korrekt erfüllen und zu einem anderen Ergebnis führen. 
%
\newpage
%
%***************************************
% ANWENDUNG
%***************************************
\section{Anwendung}
Asymmetrische Verschlüsselungen werden häufig verwendet.  Obwohl verbesserte asymmetrische Verschlüsselungen erfunden wurden, deckt der RSA-Algorithmus weiterhin einen grossen Anteil der asymmetrischen Verschlüsselungen ab.\\
Wir möchten hier einige Beispiele aufzeigen, in denen der RSA-Algorithmus verwendet wird. Typischerweise kommt ein asymmetrisches Verfahren dann zum Einsatz, wenn zwei Parteien, ohne vorherigen Kontakt, eine sichere Verbindung aufbauen möchten. Es ist naheliegend, dass im IT-Bereich, über ein Netzwerk bzw. das Internet, solche Anforderungen bestehen.
%
\subsection{SSH - Secure Shell}
Die secure shell dient zum Aufbau einer Verbindung zu einem Gerät. Dies sind meistens Netzwerkkomponente oder Server. Die shell ist eine Konsole mit der Befehle an das Gerät gesendet werden können.\\
Ohne RSA-Verschlüsselung müsste die Wartung vor Ort mit einem Kabel vorgenommen oder ein gleichbleibender Schlüssel vergeben werden. Aus Sicherheits- und Zeitgründen wären beide Möglichkeiten nicht ökonomisch.
%
\subsection{RFID}
RFID ist eine Technologie für den kontaktlosen Austausch von Informationen. Dies funktioniert über elektromagnetische Wellen. Der Einsatz ist sehr unterschiedlich. In der Logistik wird es gebraucht um Waren schneller zu finden und direkt mit Listen abzugleichen, ohne jedes Produkt einzeln über einen Strichcode zu scannen. Das RSA-Kryptosystem wird zum Austausch des Schlüssels bei RFID basierten Zugangssystemen verwendet. Ohne ein solches asymmetrisches Verfahren, könnte jemand die Verbindung abhören und die Karte somit kopieren bzw. den Schlüssel der Karte abfangen.

\subsection{PGP}
PGP ist ein Programm zur Verschlüsselung von Daten mit verschiedenen Methoden. Seit der ersten Version 1991 kann RSA verwendet werden. Das Programm wurde ausserhalb der USA weiterentwickelt und liegt seit 1998 auch Quelloffen(open source) bereit. Da in den USA Exportbeschränkungen auf Kryptographische Software verhängt wurden, durfte die Software nicht in der üblichen Form vertrieben werden. Um dieses Exportverbot zu umgehen, wurde der Quellcode der Software in Buchform vertrieben und exportiert. In Europa wurde er dann wieder abgeschrieben und kompiliert(ausführbar gemacht). 

